/**
题目:
    给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？

思路: 
    1. 头节点会变,因此需要哨兵  
    2. 快指针走n步后慢指针开始走 
    3. 当快指针到达尾部时 慢指针则在倒数n-1节点处

效果:
    执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
    内存消耗：2.2 MB, 在所有 Go 提交中击败了22.96%的用户
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
         if(!head){
            return head;
        }
        
        ListNode*fast=head;
        ListNode*slow=head;
        int bak=n;
        
        while(fast){
             
            fast=fast->next;
            if(bak--<0){
                slow=slow->next;
            }
        }
        ListNode* temp=head;
         if(bak==0){
             //说明删除的是头结点
             temp=head;
             head=head->next;
         }else{
             temp=slow->next;
		   slow->next=temp->next;
         }
        return head;
    }
};